/*
 * @lc app=leetcode.cn id=1186 lang=golang
 *
 * [1186] 删除一次得到子数组最大和
 */
package Solutions

import "math"

// @lc code=start
func maximumSum(arr []int) int {
	maxAfter := make([]int, len(arr))
	maxAfter[len(arr)-1] = arr[len(arr)-1]
	for i := len(arr) - 2; i >= 0; i-- {
		if maxAfter[i+1] > 0 {
			maxAfter[i] = maxAfter[i+1] + arr[i]
		} else {
			maxAfter[i] = arr[i]
		}
	}
	ans := -math.MaxInt64
	cache := -math.MaxInt64
	for i := 0; i < len(arr); i++ {
		if cache > 0 {
			var p = 0
			if arr[i] > 0 {
				p = cache + maxAfter[i]
			} else {
				p = cache + maxAfter[i] - arr[i]
			}
			if ans < p {
				ans = p
			}
			cache += arr[i]
		} else {
			//此时只有右侧，保证右侧选择到元素``
			if i < len(arr)-1 && maxAfter[i+1]-maxAfter[i] == arr[i] {
				if ans < maxAfter[i]-arr[i] {
					ans = maxAfter[i] - arr[i]
				}
			}
			cache = arr[i]
		}
		if ans < arr[i] {
			ans = arr[i]
		}
	}
	if len(arr) > 1 {
		if ans < maxAfter[1] {
			ans = maxAfter[1]
		}
	}
	return ans

}

// @lc code=end
